package leetcode_800;

import helpclass.TreeNode;

/**
 *@author 周杨
 *InsertIntoABinarySearchTree_701 给定一个val 插入到二叉搜索树中
 *describe:常规方法 先找到它插入的位置 就是搜索这棵树 AC 8% 也可以用非递归 无所谓
 *2018年10月10日 上午11:07:20
 */
public class InsertIntoABinarySearchTree_701 {
	public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) {
        	return new TreeNode(val);
        }
        TreeNode parent=findParent(root, val);
        if(parent.val>val)
        	parent.left=new TreeNode(val);
        else
        	parent.right=new TreeNode(val);
        return root;
    }
	
	public TreeNode findParent(TreeNode root,int val) {
		if(root.val<val) {//插到右子树里
			if(root.right==null)
				return root;
			return findParent(root.right, val);
		}
		else
			if(root.left==null)
				return root;
		return findParent(root.left, val);	
	}
}
